package minimumMoves;

import java.text.Format;
import java.util.Arrays;
import java.util.Map;

public class Solution {
//    public int minimumMoves(String s) {
//        // XXXXOOO
//        int ans = 0;
//        int i = 0;
//        while (i<s.length()) {
//            if(s.charAt(i) == 'X'){
//                i+=3; // 把后面三个元素全部转换成O
//                ans++;
//            } else {
//                i++;
//            }
//        }
//        return ans;
//    }
    private int ans = Integer.MAX_VALUE;
    public int minimumMoves(int[][] grid) {
         dfs(grid,0);
         return ans;
    }
    private void dfs(int[][] grid,int cur) {
        // 表示当前状态下的最少操作次数
        boolean bol = true;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if(grid[i][j] != 1) {
                    bol = false;
                    break;
                }
            }
        }
        if(bol) {
            ans = Math.min(ans,cur);
            return;
        }
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if(grid[i][j] > 1) {
                    for (int k = 0; k < 3; k++) {
                        for (int l = 0; l < 3; l++) {
                            if(grid[k][l] == 0) {
                                grid[i][j]--;
                                grid[k][l] = 1;
                                dfs(grid,cur+ Math.abs(i-k)+Math.abs(j-l));
                                grid[i][j]++;
                                grid[k][l] = 0;
                            }
                        }
                    }
                }
            }
        }
    }
}
